<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<title>Jamming: graph/graph.h Source File</title>

<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link href="doxygen.css" rel="stylesheet" type="text/css" />

<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="search/search.js"></script>
<script type="text/javascript">
  $(document).ready(function() { searchBox.OnSelectItem(0); });
</script>

</head>
<body>
<div id="top"><!-- do not remove this div! -->


<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  
  
  <td style="padding-left: 0.5em;">
   <div id="projectname">Jamming
   &#160;<span id="projectnumber">0.0.1</span>
   </div>
   <div id="projectbrief">An data structure and algorithm template library for quick C++ programming</div>
  </td>
  
  
  
 </tr>
 </tbody>
</table>
</div>

<!-- Generated by Doxygen 1.7.6.1 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
  <div id="navrow1" class="tabs">
    <ul class="tablist">
      <li><a href="index.html"><span>Main&#160;Page</span></a></li>
      <li><a href="annotated.html"><span>Classes</span></a></li>
      <li class="current"><a href="files.html"><span>Files</span></a></li>
      <li>
        <div id="MSearchBox" class="MSearchBoxInactive">
        <span class="left">
          <img id="MSearchSelect" src="search/mag_sel.png"
               onmouseover="return searchBox.OnSearchSelectShow()"
               onmouseout="return searchBox.OnSearchSelectHide()"
               alt=""/>
          <input type="text" id="MSearchField" value="Search" accesskey="S"
               onfocus="searchBox.OnSearchFieldFocus(true)" 
               onblur="searchBox.OnSearchFieldFocus(false)" 
               onkeyup="searchBox.OnSearchFieldChange(event)"/>
          </span><span class="right">
            <a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
          </span>
        </div>
      </li>
    </ul>
  </div>
  <div id="navrow2" class="tabs2">
    <ul class="tablist">
      <li><a href="files.html"><span>File&#160;List</span></a></li>
    </ul>
  </div>
</div>
<div class="header">
  <div class="headertitle">
<div class="title">graph/graph.h</div>  </div>
</div><!--header-->
<div class="contents">
<div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">/*</span>
<a name="l00002"></a>00002 <span class="comment"> *  @file    graph.h</span>
<a name="l00003"></a>00003 <span class="comment"> *  @author  Yi He</span>
<a name="l00004"></a>00004 <span class="comment"> *  @brief   template for graph and graph-related algorithms.</span>
<a name="l00005"></a>00005 <span class="comment"> *  @version $Id: LICENSE.h 1615 2010-10-20 19:16:35Z sobolevnrm $</span>
<a name="l00006"></a>00006 <span class="comment"> *  @attention</span>
<a name="l00007"></a>00007 <span class="comment"> *  @verbatim</span>
<a name="l00008"></a>00008 <span class="comment"> * This file is part of Jamming</span>
<a name="l00009"></a>00009 <span class="comment"> *</span>
<a name="l00010"></a>00010 <span class="comment"> * Copyright (C) 2012 - Yi He</span>
<a name="l00011"></a>00011 <span class="comment"> *</span>
<a name="l00012"></a>00012 <span class="comment"> * Jamming is free software; you can redistribute it and/or modify</span>
<a name="l00013"></a>00013 <span class="comment"> * it under the terms of the GNU General Public License as published by</span>
<a name="l00014"></a>00014 <span class="comment"> * the Free Software Foundation; either version 2 of the License, or</span>
<a name="l00015"></a>00015 <span class="comment"> * (at your option) any later version.</span>
<a name="l00016"></a>00016 <span class="comment"> *</span>
<a name="l00017"></a>00017 <span class="comment"> * Jamming is distributed in the hope that it will be useful,</span>
<a name="l00018"></a>00018 <span class="comment"> * but WITHOUT ANY WARRANTY; without even the implied warranty of</span>
<a name="l00019"></a>00019 <span class="comment"> * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the</span>
<a name="l00020"></a>00020 <span class="comment"> * GNU General Public License for more details.</span>
<a name="l00021"></a>00021 <span class="comment"> *</span>
<a name="l00022"></a>00022 <span class="comment"> * You should have received a copy of the GNU General Public License</span>
<a name="l00023"></a>00023 <span class="comment"> * along with Jamming. If not, see &lt;http://www.gnu.org/licenses/&gt;.</span>
<a name="l00024"></a>00024 <span class="comment"> * @endverbatim</span>
<a name="l00025"></a>00025 <span class="comment"> */</span>
<a name="l00026"></a>00026 
<a name="l00027"></a>00027 
<a name="l00028"></a>00028 <span class="preprocessor">#ifndef __GRAPH_H__</span>
<a name="l00029"></a>00029 <span class="preprocessor"></span><span class="preprocessor">#define __GRAPH_H__</span>
<a name="l00030"></a>00030 <span class="preprocessor"></span><span class="preprocessor">#include&lt;map&gt;</span>
<a name="l00031"></a>00031 <span class="preprocessor">#include&lt;vector&gt;</span>
<a name="l00032"></a>00032 <span class="preprocessor">#include&lt;utility&gt;</span>
<a name="l00033"></a>00033 <span class="preprocessor">#include&lt;iostream&gt;</span>
<a name="l00034"></a>00034 <span class="preprocessor">#include&lt;queue&gt;</span>
<a name="l00035"></a>00035 <span class="preprocessor">#include&lt;exception&gt;</span>
<a name="l00036"></a>00036 <span class="preprocessor">#include&lt;limits&gt;</span>
<a name="l00037"></a>00037 <span class="preprocessor">#include&lt;stack&gt;</span>
<a name="l00038"></a>00038 <span class="preprocessor">#include &quot;debug.h&quot;</span>
<a name="l00039"></a>00039 <span class="preprocessor">#include &quot;tree/disjoint_sets.h&quot;</span>
<a name="l00040"></a>00040 
<a name="l00041"></a>00041 <span class="keyword">namespace </span>graph
<a name="l00042"></a>00042 {
<a name="l00043"></a>00043 <span class="comment">/***</span>
<a name="l00044"></a>00044 <span class="comment">*  Graph data structure using adjacent list.</span>
<a name="l00045"></a>00045 <span class="comment">*/</span>
<a name="l00046"></a>00046 <span class="keyword">template</span>&lt;<span class="keyword">class</span> T&gt;
<a name="l00047"></a><a class="code" href="classgraph_1_1adjacent__graph.html">00047</a> <span class="keyword">class </span><a class="code" href="classgraph_1_1adjacent__graph.html">adjacent_graph</a>  {
<a name="l00048"></a>00048         std::vector&lt;std::map&lt;int,T&gt; &gt; g;
<a name="l00049"></a>00049         <span class="keyword">public</span>:
<a name="l00050"></a>00050         <span class="keywordtype">void</span> addedge(<span class="keywordtype">int</span> i,<span class="keywordtype">int</span> j,T v) {
<a name="l00051"></a>00051             <span class="keywordflow">if</span>(i&gt;=g.size()) g.resize(i+1,std::map&lt;int,T&gt;());
<a name="l00052"></a>00052             <span class="comment">//TODO allow i==j? </span>
<a name="l00053"></a>00053             <span class="keywordflow">if</span>(v!=0) g[i][j]=v;
<a name="l00054"></a>00054         }
<a name="l00055"></a>00055         <span class="keyword">inline</span> <span class="keywordtype">int</span> numvertex() {
<a name="l00056"></a>00056             <span class="keywordflow">return</span> g.size();
<a name="l00057"></a>00057         }
<a name="l00058"></a>00058         <span class="keyword">inline</span> T&amp; weight(<span class="keywordtype">int</span> i,<span class="keywordtype">int</span> j) {
<a name="l00059"></a>00059             <span class="comment">//TODO currently, visit noexist (i,j) will generate a element with value 0(T()). It is better to create a weight function that generate no empty space in graph.</span>
<a name="l00060"></a>00060               <span class="keywordflow">return</span> g[i][j];
<a name="l00061"></a>00061         }
<a name="l00062"></a>00062         <span class="keyword">inline</span> T&amp; operator() (<span class="keywordtype">int</span> i,<span class="keywordtype">int</span> j) {
<a name="l00063"></a>00063             <span class="keywordflow">if</span>(i &lt; g.size()) <span class="keywordflow">return</span> g[i][j];
<a name="l00064"></a>00064             <span class="keywordflow">else</span> {
<a name="l00065"></a>00065                 g.resize(i+1);
<a name="l00066"></a>00066                 <span class="keywordflow">return</span> g[i][j];
<a name="l00067"></a>00067             }
<a name="l00068"></a>00068         }
<a name="l00069"></a>00069         <span class="comment">//input&amp;output</span>
<a name="l00070"></a>00070         <span class="comment">//import from a array/matrix with N lines and M columns.</span>
<a name="l00071"></a>00071         <span class="keywordtype">void</span> <span class="keyword">import</span>(T* arr,<span class="keywordtype">int</span> N,<span class="keywordtype">int</span> M) {
<a name="l00072"></a>00072             <span class="keywordflow">for</span>(<span class="keywordtype">int</span> i=0;i&lt;N;i++)
<a name="l00073"></a>00073                 <span class="keywordflow">for</span>(<span class="keywordtype">int</span> j=0;j&lt;M;j++) {
<a name="l00074"></a>00074                     addedge(i,j,*arr);
<a name="l00075"></a>00075                     arr++;
<a name="l00076"></a>00076                 }
<a name="l00077"></a>00077         }
<a name="l00078"></a>00078         <span class="comment">//read from a stream</span>
<a name="l00079"></a>00079         <span class="keyword">template</span> &lt;<span class="keyword">class</span> inputstream&gt;
<a name="l00080"></a>00080         <span class="keywordtype">void</span> read(inputstream&amp; in,<span class="keywordtype">int</span> N,<span class="keywordtype">int</span> M) {
<a name="l00081"></a>00081             T v;
<a name="l00082"></a>00082             <span class="keywordflow">for</span>(<span class="keywordtype">int</span> i=0;i&lt;N;i++){
<a name="l00083"></a>00083                std::string l;
<a name="l00084"></a>00084               <span class="keywordflow">for</span>(<span class="keywordtype">int</span> j=0;j&lt;M;j++) {
<a name="l00085"></a>00085                 in&gt;&gt;v;
<a name="l00086"></a>00086                 addedge(i,j,v);
<a name="l00087"></a>00087               }
<a name="l00088"></a>00088               getline(in,l);
<a name="l00089"></a>00089             }
<a name="l00090"></a>00090         }
<a name="l00091"></a>00091         <span class="keyword">template</span> &lt;<span class="keyword">class</span> outputstream&gt;
<a name="l00092"></a>00092         <span class="keywordtype">void</span> print_edges(outputstream &amp;out) {
<a name="l00093"></a>00093             <span class="keywordtype">int</span> w=g.size();
<a name="l00094"></a>00094             <span class="keywordflow">for</span>(<span class="keywordtype">int</span> i=0;i&lt;w;i++) {
<a name="l00095"></a>00095                 out&lt;&lt;i&lt;&lt;<span class="stringliteral">&quot; : &quot;</span>;
<a name="l00096"></a>00096                 <span class="keywordflow">for</span>(<span class="keyword">typename</span> std::map&lt;int,T&gt;::iterator it=g[i].begin();it!=g[i].end();it++) {
<a name="l00097"></a>00097                     <span class="keywordflow">if</span>(it-&gt;second != T()) out&lt;&lt;<span class="stringliteral">&quot;(&quot;</span>&lt;&lt;it-&gt;first&lt;&lt;<span class="stringliteral">&quot;,&quot;</span>&lt;&lt;it-&gt;second&lt;&lt;<span class="stringliteral">&quot;)&quot;</span>;
<a name="l00098"></a>00098                     <span class="keywordflow">else</span> g[i].erase(it);
<a name="l00099"></a>00099                 }
<a name="l00100"></a>00100                 out&lt;&lt;std::endl;
<a name="l00101"></a>00101             }
<a name="l00102"></a>00102         }
<a name="l00103"></a>00103         <span class="keyword">template</span> &lt;<span class="keyword">class</span> outputstream&gt;
<a name="l00104"></a>00104         <span class="keywordtype">void</span> print_map(outputstream &amp;out) {
<a name="l00105"></a>00105             <span class="keywordtype">int</span> w=g.size();
<a name="l00106"></a>00106             <span class="keywordflow">for</span>(<span class="keywordtype">int</span> i=0;i&lt;w;i++) {
<a name="l00107"></a>00107               <span class="keywordflow">for</span>(<span class="keywordtype">int</span> j=0;j&lt;w;j++)
<a name="l00108"></a>00108                 out&lt;&lt;g[i][j]&lt;&lt;<span class="stringliteral">&quot; &quot;</span>;
<a name="l00109"></a>00109                out&lt;&lt;std::endl;
<a name="l00110"></a>00110             }
<a name="l00111"></a>00111         }
<a name="l00112"></a>00112         <span class="comment">//iterator </span>
<a name="l00113"></a><a class="code" href="classgraph_1_1adjacent__graph_1_1edge__iterator.html">00113</a>         <span class="keyword">class </span><a class="code" href="classgraph_1_1adjacent__graph_1_1edge__iterator.html">edge_iterator</a> {
<a name="l00114"></a>00114             <a class="code" href="classgraph_1_1adjacent__graph.html">adjacent_graph&lt;T&gt;</a>* pG; <span class="comment">// graph pointed to.</span>
<a name="l00115"></a>00115             <span class="keyword">typename</span> std::map&lt;int,T&gt;::iterator pC; <span class="comment">//current position</span>
<a name="l00116"></a>00116             <span class="keywordtype">int</span> pV; <span class="comment">//source vertex pointed to. </span>
<a name="l00117"></a>00117             <span class="comment">//condense zero edges</span>
<a name="l00118"></a>00118             <span class="keyword">inline</span> <span class="keywordtype">void</span> condense() {
<a name="l00119"></a>00119                     <span class="comment">//Remove edge that equals T() (-&gt; 0 -&gt; no connection).</span>
<a name="l00120"></a>00120                     <span class="keywordflow">while</span>(pC-&gt;second==T()) {
<a name="l00121"></a>00121                         <span class="keywordflow">if</span>(pC==pG-&gt;g[pV].end()) <span class="keywordflow">break</span>;
<a name="l00122"></a>00122                         pG-&gt;g[pV].erase(pC++);
<a name="l00123"></a>00123                     }
<a name="l00124"></a>00124             }
<a name="l00125"></a>00125             <span class="keyword">public</span>:
<a name="l00126"></a>00126                 <a class="code" href="classgraph_1_1adjacent__graph_1_1edge__iterator.html">edge_iterator</a>();
<a name="l00127"></a>00127                 <a class="code" href="classgraph_1_1adjacent__graph_1_1edge__iterator.html">edge_iterator</a>(<a class="code" href="classgraph_1_1adjacent__graph.html">adjacent_graph&lt;T&gt;</a>* p,<span class="keywordtype">int</span> v,<span class="keyword">typename</span> std::map&lt;int,T&gt;::iterator c) : pG(p),pV(v),pC(c) {}
<a name="l00128"></a>00128                 <span class="keyword">inline</span> <span class="keywordtype">int</span> vertex() {
<a name="l00129"></a>00129                     condense();
<a name="l00130"></a>00130                     <span class="keywordflow">return</span> pC-&gt;first;
<a name="l00131"></a>00131                 }
<a name="l00132"></a>00132                 <span class="keyword">inline</span> T length() {
<a name="l00133"></a>00133                     condense();
<a name="l00134"></a>00134                     <span class="keywordflow">return</span> pC-&gt;second;
<a name="l00135"></a>00135                 }
<a name="l00136"></a>00136                <a class="code" href="classgraph_1_1adjacent__graph_1_1edge__iterator.html">edge_iterator</a>&amp; operator++ () {
<a name="l00137"></a>00137                     <span class="keywordflow">if</span>(pC-&gt;second!=T()) pC++;
<a name="l00138"></a>00138                     <span class="keywordflow">else</span> <span class="keywordflow">do</span> {
<a name="l00139"></a>00139                     <span class="comment">//condense zero edges</span>
<a name="l00140"></a>00140                         <span class="keywordflow">if</span>(pC==pG-&gt;g[pV].end()) <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l00141"></a>00141                         pG-&gt;g[pV].erase(pC++);
<a name="l00142"></a>00142                     } <span class="keywordflow">while</span>(pC-&gt;second==T());
<a name="l00143"></a>00143                     <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l00144"></a>00144                 }
<a name="l00145"></a>00145                 <span class="comment">//TODO implement it++? (force to use ++it so that there is no additional performance cost?)</span>
<a name="l00146"></a>00146                 <span class="keywordtype">bool</span> operator!= (<span class="keyword">const</span> <a class="code" href="classgraph_1_1adjacent__graph_1_1edge__iterator.html">edge_iterator</a>&amp; ref) {
<a name="l00147"></a>00147                     condense();
<a name="l00148"></a>00148                     <span class="keywordflow">if</span>(pG==ref.pG &amp;&amp; pV==ref.pV &amp;&amp; pC==ref.pC) <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00149"></a>00149                     <span class="keywordflow">else</span> <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00150"></a>00150                 }
<a name="l00151"></a>00151                 <span class="keywordtype">bool</span> operator==(<span class="keyword">const</span> <a class="code" href="classgraph_1_1adjacent__graph_1_1edge__iterator.html">edge_iterator</a>&amp; ref) {
<a name="l00152"></a>00152                     condense();
<a name="l00153"></a>00153                     <span class="keywordflow">if</span>(pG==ref.pG &amp;&amp; pV==ref.pV &amp;&amp; pC==ref.pC) <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00154"></a>00154                     <span class="keywordflow">else</span> <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00155"></a>00155                 }
<a name="l00156"></a>00156                 <span class="comment">//TODO implement operator* &amp; operator-&gt;</span>
<a name="l00157"></a>00157                 std::pair&lt;const int,T&gt; &amp; operator* () {
<a name="l00158"></a>00158                     condense();
<a name="l00159"></a>00159                     <span class="keywordflow">return</span> *pC;
<a name="l00160"></a>00160                 }
<a name="l00161"></a>00161                 <span class="keyword">typename</span> std::map&lt;int,T&gt;::iterator operator-&gt;() {
<a name="l00162"></a>00162                     condense();
<a name="l00163"></a>00163                     <span class="keywordflow">return</span> pC;
<a name="l00164"></a>00164                 }
<a name="l00165"></a>00165         };
<a name="l00166"></a>00166         <a class="code" href="classgraph_1_1adjacent__graph_1_1edge__iterator.html">edge_iterator</a> first_edge(<span class="keywordtype">int</span> v) {
<a name="l00167"></a>00167             <span class="keywordflow">return</span> <a class="code" href="classgraph_1_1adjacent__graph_1_1edge__iterator.html">edge_iterator</a>(<span class="keyword">this</span>,v,g[v].begin());
<a name="l00168"></a>00168         }
<a name="l00169"></a>00169         edge_iterator end_edge(<span class="keywordtype">int</span> v) {
<a name="l00170"></a>00170             <span class="keywordflow">return</span> edge_iterator(<span class="keyword">this</span>,v,g[v].end());
<a name="l00171"></a>00171         }
<a name="l00172"></a>00172 }; 
<a name="l00173"></a>00173 
<a name="l00174"></a>00174 
<a name="l00178"></a>00178 <span class="comment">// exceptions for explorer</span>
<a name="l00179"></a><a class="code" href="classgraph_1_1GraphHasLoop.html">00179</a> <span class="keyword">class </span><a class="code" href="classgraph_1_1GraphHasLoop.html">GraphHasLoop</a> : <span class="keyword">public</span> std::exception {};
<a name="l00180"></a>00180 <span class="comment">// Helper classes for explorer</span>
<a name="l00181"></a>00181 <span class="comment">//Conditions to end dfs/bfs search </span>
<a name="l00182"></a>00182 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt;
<a name="l00183"></a><a class="code" href="classgraph_1_1reached__at.html">00183</a> <span class="keyword">class </span><a class="code" href="classgraph_1_1reached__at.html">reached_at</a> {
<a name="l00184"></a>00184         <span class="keywordtype">int</span> t;
<a name="l00185"></a>00185         <span class="keyword">public</span>:
<a name="l00186"></a>00186             <a class="code" href="classgraph_1_1reached__at.html">reached_at</a>(<span class="keywordtype">int</span> ter) : t(ter) {};
<a name="l00187"></a>00187         <span class="keywordtype">bool</span> operator() (<span class="keywordtype">int</span> v,<span class="keywordtype">int</span> prev, <span class="keywordtype">bool</span> hasOutEdge) {
<a name="l00188"></a>00188                 <span class="keywordflow">return</span> (v==t);
<a name="l00189"></a>00189             }
<a name="l00190"></a>00190         <span class="keywordtype">bool</span> operator() (std::vector&lt;T&gt;&amp; dist) {
<a name="l00191"></a>00191             <span class="keywordflow">if</span>(dist[t]&lt;std::numeric_limits&lt;T&gt;::max()) <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00192"></a>00192             <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00193"></a>00193         }
<a name="l00194"></a>00194 };
<a name="l00195"></a>00195 <span class="keywordtype">bool</span> visited_all(<span class="keywordtype">int</span> v,<span class="keywordtype">int</span> prev, <span class="keywordtype">bool</span> hasOutEdge) { <span class="keywordflow">return</span> <span class="keyword">false</span>;}
<a name="l00196"></a><a class="code" href="classgraph_1_1terminate__at.html">00196</a> <span class="keyword">class </span><a class="code" href="classgraph_1_1terminate__at.html">terminate_at</a>{
<a name="l00197"></a>00197         <span class="keywordtype">int</span>&amp; t;
<a name="l00198"></a>00198         <span class="keyword">public</span>:
<a name="l00199"></a>00199             <a class="code" href="classgraph_1_1terminate__at.html">terminate_at</a>(<span class="keywordtype">int</span>&amp; ter) : t(ter) {};
<a name="l00200"></a>00200         <span class="keywordtype">bool</span> operator() (<span class="keywordtype">int</span> v,<span class="keywordtype">int</span> prev, <span class="keywordtype">bool</span> hasOutEdge) {
<a name="l00201"></a>00201                 t=v;
<a name="l00202"></a>00202                 <span class="keywordflow">return</span> !hasOutEdge;
<a name="l00203"></a>00203             }
<a name="l00204"></a>00204 };
<a name="l00205"></a>00205 
<a name="l00206"></a>00206 <span class="comment">//conditions to visit an edge in dfs/bfs search </span>
<a name="l00207"></a>00207 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt;
<a name="l00208"></a><a class="code" href="classgraph_1_1hasedge.html">00208</a> <span class="keyword">class </span><a class="code" href="classgraph_1_1hasedge.html">hasedge</a> {
<a name="l00209"></a>00209     <span class="keyword">public</span>:
<a name="l00210"></a>00210     <span class="keywordtype">bool</span> operator()(<span class="keywordtype">int</span> v,<span class="keywordtype">int</span> prev,T&amp; edge) { <span class="keywordflow">return</span> (edge!=T());}
<a name="l00211"></a>00211 };
<a name="l00212"></a>00212 
<a name="l00213"></a>00213 
<a name="l00214"></a>00214 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T,<span class="keyword">class</span> container=<span class="keyword">class</span> adjacent_graph&lt;T&gt; &gt;
<a name="l00215"></a><a class="code" href="classgraph_1_1explorer.html">00215</a> <span class="keyword">class </span><a class="code" href="classgraph_1_1explorer.html">explorer</a> {
<a name="l00216"></a>00216     T Inf;
<a name="l00217"></a>00217     std::vector&lt;std::vector&lt;T&gt; &gt; dist;
<a name="l00218"></a>00218     std::vector&lt;std::vector&lt;int&gt; &gt; prev;
<a name="l00219"></a>00219     container&amp; g; 
<a name="l00220"></a>00220     <span class="keyword">public</span>:
<a name="l00221"></a>00221     <a class="code" href="classgraph_1_1explorer.html">explorer</a>() {
<a name="l00222"></a>00222         Inf=std::numeric_limits&lt;T&gt;::max();
<a name="l00223"></a>00223     }
<a name="l00224"></a>00224     <a class="code" href="classgraph_1_1explorer.html">explorer</a>(container &amp;c) : g(c) {
<a name="l00225"></a>00225         Inf=std::numeric_limits&lt;T&gt;::max();
<a name="l00226"></a>00226     }
<a name="l00230"></a>00230     <span class="keyword">template</span> &lt;<span class="keyword">class</span> _Vertex_found_func ,<span class="keyword">class</span> _Edge_check_func &gt;
<a name="l00231"></a><a class="code" href="classgraph_1_1explorer.html#aa967169a22798c9745c098d542f22c25">00231</a>     <span class="keywordtype">bool</span> <a class="code" href="classgraph_1_1explorer.html#aa967169a22798c9745c098d542f22c25">bfs_until</a>(<span class="keywordtype">int</span> s,_Vertex_found_func found,_Edge_check_func edge_check) {
<a name="l00232"></a>00232         <span class="keywordtype">int</span> u,v;
<a name="l00233"></a>00233         std::queue&lt;int &gt; q; 
<a name="l00234"></a>00234         <span class="keywordflow">if</span>(s&gt;=dist.size()) dist.resize(s+1);
<a name="l00235"></a>00235         <span class="keywordflow">if</span>(s&gt;=prev.size()) prev.resize(s+1);
<a name="l00236"></a>00236         prev[s]=<span class="keyword">typename</span> std::vector&lt;int&gt; (g.numvertex(),-1);
<a name="l00237"></a>00237         <span class="keyword">typename</span> std::vector&lt;bool&gt; visited(g.numvertex(),0);
<a name="l00238"></a>00238         visited[s]=<span class="keyword">true</span>;
<a name="l00239"></a>00239         q.push(s);
<a name="l00240"></a>00240         <span class="keywordflow">while</span>(!q.empty()) {
<a name="l00241"></a>00241             u=q.front();
<a name="l00242"></a>00242             q.pop();
<a name="l00243"></a>00243             <span class="keywordtype">bool</span> hasOutEdge=<span class="keyword">false</span>;
<a name="l00244"></a>00244             <span class="keywordflow">for</span>(<span class="keyword">typename</span> container::edge_iterator it=g.first_edge(u);it!=g.end_edge(u);++it) {
<a name="l00245"></a>00245                 v=it.vertex();
<a name="l00246"></a>00246                 T w=it.length(); <span class="comment">//TODO edge requirment-&gt; comp() function.</span>
<a name="l00247"></a>00247                 <span class="keywordflow">if</span>(!visited[v]&amp;&amp;edge_check(v,u,w)) {
<a name="l00248"></a>00248                     prev[s][v]=u;visited[v]=<span class="keyword">true</span>;
<a name="l00249"></a>00249                     hasOutEdge=<span class="keyword">true</span>;
<a name="l00250"></a>00250                     q.push(v);
<a name="l00251"></a>00251                 }
<a name="l00252"></a>00252             }
<a name="l00253"></a>00253             <span class="keywordflow">if</span>(found(u,prev[s][u],hasOutEdge)&amp;&amp;u!=s) <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00254"></a>00254         }
<a name="l00255"></a>00255         <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00256"></a>00256     }
<a name="l00257"></a>00257     <span class="keyword">template</span> &lt;<span class="keyword">class</span> _Vertex_found_func &gt;
<a name="l00258"></a>00258     <span class="keywordtype">bool</span> <a class="code" href="classgraph_1_1explorer.html#aa967169a22798c9745c098d542f22c25">bfs_until</a>(<span class="keywordtype">int</span> s,<span class="keyword">const</span> _Vertex_found_func&amp; found) {
<a name="l00259"></a>00259         <span class="keywordflow">return</span> <a class="code" href="classgraph_1_1explorer.html#aa967169a22798c9745c098d542f22c25">bfs_until</a>(s,found,<a class="code" href="classgraph_1_1hasedge.html">hasedge&lt;T&gt;</a>());
<a name="l00260"></a>00260     }
<a name="l00261"></a>00261     <span class="keywordtype">bool</span> bfs(<span class="keywordtype">int</span> s,<span class="keywordtype">int</span> t=-1) {
<a name="l00262"></a>00262         <span class="keywordflow">return</span> <a class="code" href="classgraph_1_1explorer.html#aa967169a22798c9745c098d542f22c25">bfs_until</a>(s,reached_at&lt;T&gt;(t),hasedge&lt;T&gt;());
<a name="l00263"></a>00263     }
<a name="l00264"></a>00264     <span class="comment">// dfs walker </span>
<a name="l00265"></a>00265     <span class="keyword">template</span> &lt;<span class="keyword">class</span> _Vertex_found_func ,<span class="keyword">class</span> _Edge_check_func &gt;
<a name="l00266"></a>00266     <span class="keywordtype">bool</span> dfs_until(<span class="keywordtype">int</span> s,_Vertex_found_func found,_Edge_check_func edge_check) {
<a name="l00267"></a>00267         <span class="keywordflow">if</span>(s&gt;=dist.size()) dist.resize(s+1);
<a name="l00268"></a>00268         <span class="keywordflow">if</span>(s&gt;=prev.size()) prev.resize(s+1);
<a name="l00269"></a>00269         std::stack&lt;int&gt; q;
<a name="l00270"></a>00270         prev[s]=std::vector&lt;int&gt; (g.numvertex(),-1);
<a name="l00271"></a>00271         std::vector&lt;bool&gt; visited(g.numvertex(),0);
<a name="l00272"></a>00272         q.push(s);
<a name="l00273"></a>00273         visited[s]=<span class="keyword">true</span>;
<a name="l00274"></a>00274         <span class="keywordflow">while</span>(!q.empty()) {
<a name="l00275"></a>00275             <span class="keywordtype">int</span> u=q.top(); 
<a name="l00276"></a>00276             <span class="keywordtype">bool</span> hasOutEdge=<span class="keyword">false</span>;
<a name="l00277"></a>00277             <span class="keywordflow">for</span>(<span class="keyword">typename</span> container::edge_iterator it=g.first_edge(u);it!=g.end_edge(u);++it) {
<a name="l00278"></a>00278                 <span class="keywordtype">int</span> v=it.vertex();
<a name="l00279"></a>00279                 T w=it.length(); <span class="comment">//TODO edge requirment-&gt; comp() function.</span>
<a name="l00280"></a>00280                 <span class="keywordflow">if</span>(!visited[v]&amp;&amp;edge_check(v,u,w)) {
<a name="l00281"></a>00281                     prev[s][v]=u;visited[v]=<span class="keyword">true</span>;
<a name="l00282"></a>00282                     q.push(v);
<a name="l00283"></a>00283                     hasOutEdge=<span class="keyword">true</span>;
<a name="l00284"></a>00284                 }
<a name="l00285"></a>00285             }
<a name="l00286"></a>00286             <span class="keywordflow">if</span>(found(u,prev[s][u],hasOutEdge)&amp;&amp;u!=s) <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00287"></a>00287             <span class="keywordflow">if</span>(!hasOutEdge) q.pop();
<a name="l00288"></a>00288         }
<a name="l00289"></a>00289         <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00290"></a>00290     }
<a name="l00291"></a>00291     <span class="keyword">template</span> &lt;<span class="keyword">class</span> _Vertex_found_func &gt;
<a name="l00292"></a>00292     <span class="keywordtype">bool</span> dfs_until(<span class="keywordtype">int</span> s,<span class="keyword">const</span> _Vertex_found_func&amp; found) {
<a name="l00293"></a>00293         <span class="keywordflow">return</span> dfs_until(s,found,hasedge&lt;T&gt;());
<a name="l00294"></a>00294     }
<a name="l00295"></a>00295     <span class="keywordtype">bool</span> dfs(<span class="keywordtype">int</span> s,<span class="keywordtype">int</span> t=-1) {
<a name="l00296"></a>00296         <span class="keywordflow">return</span> dfs_until(s,reached_at&lt;T&gt;(t),hasedge&lt;T&gt;());
<a name="l00297"></a>00297     }
<a name="l00298"></a>00298     <span class="comment">//shortest distance walkers</span>
<a name="l00303"></a>00303 <span class="comment"></span>    <span class="keyword">template</span> &lt;<span class="keyword">class</span> _Vertex_found_func &gt;
<a name="l00304"></a><a class="code" href="classgraph_1_1explorer.html#afa222404714e24e17ccf7e1edd5898c0">00304</a>     <span class="keywordtype">bool</span> <a class="code" href="classgraph_1_1explorer.html#afa222404714e24e17ccf7e1edd5898c0">dijkstra_until</a>(<span class="keywordtype">int</span> s,_Vertex_found_func found) {
<a name="l00305"></a>00305         T w;
<a name="l00306"></a>00306         <span class="keywordflow">if</span>(s&gt;=dist.size()) dist.resize(s+1);
<a name="l00307"></a>00307         <span class="keywordflow">if</span>(s&gt;=prev.size()) prev.resize(s+1);
<a name="l00308"></a>00308         dist[s]=std::vector&lt;T&gt;(g.numvertex(),Inf);
<a name="l00309"></a>00309         prev[s]=std::vector&lt;int&gt;(g.numvertex(),-1);
<a name="l00310"></a>00310         <span class="comment">//if(s&gt;=g.numvertex()) throw GraphHasLoop();</span>
<a name="l00311"></a>00311         dist[s][s]=T();
<a name="l00312"></a>00312         <span class="keyword">typename</span> std::priority_queue&lt;std::pair&lt;T,int&gt; ,std::vector&lt;std::pair&lt;T,int&gt; &gt;, std::greater&lt;std::pair&lt;T,int&gt; &gt; &gt; q;
<a name="l00313"></a>00313         q.push(std::pair&lt;T,int&gt;(T(),s));
<a name="l00314"></a>00314         std::vector&lt;bool&gt; visited(g.numvertex(),<span class="keyword">false</span>);
<a name="l00315"></a>00315         <span class="keywordflow">while</span>(!q.empty()) {
<a name="l00316"></a>00316             std::pair&lt;T,int&gt; tV=q.top(); q.pop(); <span class="comment">//top vertex.</span>
<a name="l00317"></a>00317             <span class="keywordtype">int</span> u=tV.second;
<a name="l00318"></a>00318             visited[u]=1;
<a name="l00319"></a>00319             <span class="keywordflow">for</span>(<span class="keyword">typename</span> container::edge_iterator it=g.first_edge(u);it!=g.end_edge(u);++it) {
<a name="l00320"></a>00320                 <span class="keywordtype">int</span> v=it.vertex(); w=it.length(); 
<a name="l00321"></a>00321                 <span class="comment">//TODO ? what about formula description? redefine its length?</span>
<a name="l00322"></a>00322                 <span class="keywordflow">if</span>(visited[v]) <span class="keywordflow">continue</span>;
<a name="l00323"></a>00323                 <span class="comment">//relax</span>
<a name="l00324"></a>00324                 <span class="keywordflow">if</span>( dist[s][v] &gt; dist[s][u]+w) {
<a name="l00325"></a>00325                      dist[s][v]= dist[s][u]+w; prev[s][v]=u;
<a name="l00326"></a>00326                 }
<a name="l00327"></a>00327                q.push(std::pair&lt;T,int&gt;(dist[s][v],v));
<a name="l00328"></a>00328             }
<a name="l00329"></a>00329         }
<a name="l00330"></a>00330         <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00331"></a>00331     }
<a name="l00332"></a>00332     <span class="keywordtype">bool</span> dijkstra(<span class="keywordtype">int</span> s,<span class="keywordtype">int</span> t=-1) {
<a name="l00333"></a>00333         <span class="keywordflow">return</span> <a class="code" href="classgraph_1_1explorer.html#afa222404714e24e17ccf7e1edd5898c0">dijkstra_until</a>(s,<a class="code" href="classgraph_1_1reached__at.html">reached_at&lt;T&gt;</a>(t));
<a name="l00334"></a>00334     }
<a name="l00339"></a>00339     <span class="keyword">template</span> &lt;<span class="keyword">class</span> _Vertex_found_func &gt;
<a name="l00340"></a><a class="code" href="classgraph_1_1explorer.html#aac330e1714dc9b43b96bfbec6fa6a696">00340</a>     <span class="keywordtype">bool</span> <a class="code" href="classgraph_1_1explorer.html#aac330e1714dc9b43b96bfbec6fa6a696">spfa_until</a>(<span class="keywordtype">int</span> s,_Vertex_found_func found) {
<a name="l00341"></a>00341         <span class="keywordflow">if</span>(s&gt;=dist.size()) dist.resize(s+1);
<a name="l00342"></a>00342         <span class="keywordflow">if</span>(s&gt;=prev.size()) prev.resize(s+1);
<a name="l00343"></a>00343         dist[s]=std::vector&lt;T&gt;(g.numvertex(),Inf);
<a name="l00344"></a>00344         prev[s]=std::vector&lt;int&gt;(g.numvertex(),-1);
<a name="l00345"></a>00345         dist[s][s]=0;
<a name="l00346"></a>00346         std::deque&lt;int&gt; q;
<a name="l00347"></a>00347         q.push_back(s);
<a name="l00348"></a>00348         std::vector&lt;bool&gt; inQ(g.numvertex(),0);
<a name="l00349"></a>00349         <span class="keywordflow">while</span>( q.size()!=0) {
<a name="l00350"></a>00350             <span class="keywordtype">int</span> u=q.front(); q.pop_front(); inQ[u]=<span class="keyword">false</span>;
<a name="l00351"></a>00351             <span class="comment">//if(u==t) return true;</span>
<a name="l00352"></a>00352             <span class="comment">//TODO negative loop check?</span>
<a name="l00353"></a>00353             <span class="keywordflow">for</span>(<span class="keyword">typename</span> container::edge_iterator it=g.first_edge(u);it!=g.end_edge(u);++it) {
<a name="l00354"></a>00354                 <span class="keywordtype">int</span> v=it.vertex(); T w=it.length(); <span class="comment">//TODO what about formula description?</span>
<a name="l00355"></a>00355                 <span class="comment">//relax</span>
<a name="l00356"></a>00356                 <span class="keywordflow">if</span>( dist[s][v] &gt; dist[s][u]+w) {
<a name="l00357"></a>00357                     dist[s][v]=dist[s][u]+w; prev[s][v]=u;
<a name="l00358"></a>00358                      <span class="keywordflow">if</span>(!inQ[v]) {
<a name="l00359"></a>00359                         inQ[v]=<span class="keyword">true</span>;
<a name="l00360"></a>00360                         <span class="keywordflow">if</span>(q.size()!=0) {
<a name="l00361"></a>00361                             <span class="keywordflow">if</span>(dist[s][v]&gt;dist[s][q.front()]) q.push_back(v);
<a name="l00362"></a>00362                             <span class="keywordflow">else</span> q.push_front(v);
<a name="l00363"></a>00363                         } <span class="keywordflow">else</span> {
<a name="l00364"></a>00364                             q.push_back(v);
<a name="l00365"></a>00365                         }
<a name="l00366"></a>00366                      }
<a name="l00367"></a>00367                 }
<a name="l00368"></a>00368             }
<a name="l00369"></a>00369         }
<a name="l00370"></a>00370         <span class="keywordflow">if</span>(found(dist[s])) <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00371"></a>00371         <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00372"></a>00372     }
<a name="l00373"></a>00373     <span class="keywordtype">bool</span> spfa(<span class="keywordtype">int</span> s,<span class="keywordtype">int</span> t=-1) {
<a name="l00374"></a>00374         <span class="keywordflow">return</span> <a class="code" href="classgraph_1_1explorer.html#aac330e1714dc9b43b96bfbec6fa6a696">spfa_until</a>(s,<a class="code" href="classgraph_1_1reached__at.html">reached_at&lt;T&gt;</a>(t));
<a name="l00375"></a>00375     }
<a name="l00380"></a><a class="code" href="classgraph_1_1explorer.html#a0ccb2c39e19b5dc568ea046bd207f588">00380</a>     <span class="keywordtype">void</span> <a class="code" href="classgraph_1_1explorer.html#a0ccb2c39e19b5dc568ea046bd207f588">flyod</a>() {
<a name="l00381"></a>00381         dist=std::vector&lt;std::vector&lt;T&gt; &gt; (g.numvertex(), std::vector&lt;T&gt;(g.numvertex(),Inf) );
<a name="l00382"></a>00382         <span class="comment">//prev=std::vector&lt;std::vector&lt;int&gt; &gt; (g.numvertex(), std::vector&lt;int&gt;(g.numvertex(),-1) );</span>
<a name="l00383"></a>00383         <span class="keywordflow">for</span>(<span class="keywordtype">int</span> i=0;i&lt;g.numvertex();i++) 
<a name="l00384"></a>00384           <span class="keywordflow">for</span>(<span class="keywordtype">int</span> j=0;j&lt;g.numvertex();j++) {
<a name="l00385"></a>00385             <span class="keywordflow">if</span>(i==j) dist[i][j]=0;
<a name="l00386"></a>00386             <span class="keywordflow">else</span> <span class="keywordflow">if</span>(g.weight(i,j)!=0) dist[i][j]=g.weight(i,j);
<a name="l00387"></a>00387             <span class="keywordflow">else</span> dist[i][j]=Inf;
<a name="l00388"></a>00388         }
<a name="l00389"></a>00389         <span class="keywordflow">for</span>(<span class="keywordtype">int</span> k=0;k&lt;g.numvertex();k++) 
<a name="l00390"></a>00390            <span class="keywordflow">for</span>(<span class="keywordtype">int</span> i=0;i&lt;g.numvertex();i++) 
<a name="l00391"></a>00391             <span class="keywordflow">if</span>(i!=k) 
<a name="l00392"></a>00392               <span class="keywordflow">for</span>(<span class="keywordtype">int</span> j=0;j&lt;g.numvertex();j++) {
<a name="l00393"></a>00393                 <span class="keywordflow">if</span>(i!=j&amp;&amp;j!=k &amp;&amp; dist[i][k]&lt; Inf &amp;&amp; dist[k][j]&lt; Inf \
<a name="l00394"></a>00394                     &amp;&amp; dist[i][k]+dist[k][j]&lt;dist[i][j]) {
<a name="l00395"></a>00395                     dist[i][j]=dist[i][k]+dist[k][j];
<a name="l00396"></a>00396                     <span class="comment">//path[i][j]=k;</span>
<a name="l00397"></a>00397                 }
<a name="l00398"></a>00398               }
<a name="l00399"></a>00399     }
<a name="l00400"></a>00400     <span class="comment">//output distance</span>
<a name="l00401"></a>00401     <span class="keyword">inline</span> T distance(<span class="keywordtype">int</span> s,<span class="keywordtype">int</span> t) {
<a name="l00402"></a>00402         <span class="keywordflow">return</span> dist[s][t];
<a name="l00403"></a>00403     }
<a name="l00404"></a>00404     <span class="comment">// empty the space occupied by explorer</span>
<a name="l00405"></a>00405     <span class="keywordtype">void</span> clear() {
<a name="l00406"></a>00406         dist.resize(0);
<a name="l00407"></a>00407         prev.resize(0);
<a name="l00408"></a>00408     }
<a name="l00409"></a>00409     <span class="comment">//path iterator</span>
<a name="l00410"></a><a class="code" href="classgraph_1_1explorer_1_1path__iterator.html">00410</a>     <span class="keyword">class </span><a class="code" href="classgraph_1_1explorer_1_1path__iterator.html">path_iterator</a> {
<a name="l00411"></a>00411         container&amp; g;
<a name="l00412"></a>00412         std::vector&lt;int&gt;&amp; prev;
<a name="l00413"></a>00413         <span class="keywordtype">int</span> cur_pos; <span class="comment">//point to current position;</span>
<a name="l00414"></a>00414         <span class="keyword">public</span>:
<a name="l00415"></a>00415             <a class="code" href="classgraph_1_1explorer_1_1path__iterator.html">path_iterator</a>(container&amp; g,std::vector&lt;int&gt;&amp; chain,<span class="keywordtype">int</span> pos) :g(g),prev(chain),cur_pos(pos) {};
<a name="l00416"></a>00416             <span class="keywordtype">bool</span> operator!=(<span class="keyword">const</span> <a class="code" href="classgraph_1_1explorer_1_1path__iterator.html">path_iterator</a>&amp; ref) {
<a name="l00417"></a>00417                 <span class="keywordflow">if</span>(cur_pos==ref.cur_pos) <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00418"></a>00418                 <span class="keywordflow">else</span> <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00419"></a>00419             }
<a name="l00420"></a>00420             <a class="code" href="classgraph_1_1explorer_1_1path__iterator.html">path_iterator</a>&amp; operator --() {
<a name="l00421"></a>00421                 cur_pos=prev[cur_pos];
<a name="l00422"></a>00422                 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l00423"></a>00423             }
<a name="l00424"></a>00424             <span class="keywordtype">int</span> vertex() {
<a name="l00425"></a>00425                 <span class="keywordflow">return</span> cur_pos;
<a name="l00426"></a>00426             }
<a name="l00427"></a>00427             <span class="keywordtype">int</span> operator*() {
<a name="l00428"></a>00428                 <span class="keywordflow">return</span> cur_pos;
<a name="l00429"></a>00429             }
<a name="l00430"></a>00430             T&amp; operator-() {
<a name="l00431"></a>00431                 <span class="keywordflow">return</span> g.weight(prev[cur_pos],cur_pos);
<a name="l00432"></a>00432             }
<a name="l00433"></a>00433             T&amp; operator+() {
<a name="l00434"></a>00434                 <span class="keywordflow">return</span> g.weight(cur_pos,prev[cur_pos]);
<a name="l00435"></a>00435             }
<a name="l00436"></a>00436     };
<a name="l00437"></a>00437     <a class="code" href="classgraph_1_1explorer_1_1path__iterator.html">path_iterator</a> path_begin(<span class="keywordtype">int</span> s,<span class="keywordtype">int</span> t=-1) {
<a name="l00438"></a>00438         <span class="keywordflow">return</span> <a class="code" href="classgraph_1_1explorer_1_1path__iterator.html">path_iterator</a>(g,prev[s],s);
<a name="l00439"></a>00439     };
<a name="l00440"></a>00440     path_iterator path_end(<span class="keywordtype">int</span> s,<span class="keywordtype">int</span> t=-1) {
<a name="l00441"></a>00441         <span class="keywordflow">if</span>(t&lt;0);
<a name="l00442"></a>00442         <span class="keywordflow">return</span> path_iterator(g,prev[s],t);
<a name="l00443"></a>00443     };
<a name="l00444"></a>00444 };
<a name="l00445"></a>00445 
<a name="l00446"></a>00446 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T,<span class="keyword">class</span> container=<span class="keyword">class</span> adjacent_graph&lt;T&gt; &gt;
<a name="l00447"></a><a class="code" href="classgraph_1_1connect.html">00447</a> <span class="keyword">class </span><a class="code" href="classgraph_1_1connect.html">connect</a> {
<a name="l00448"></a>00448     T Inf;
<a name="l00449"></a>00449     container&amp; g; <span class="comment">//original graph.</span>
<a name="l00450"></a>00450     <span class="keyword">public</span>:
<a name="l00451"></a>00451     <a class="code" href="classgraph_1_1connect.html">connect</a>();
<a name="l00452"></a><a class="code" href="classgraph_1_1connect.html#a1d9995deb5eb3bdd3af6029e4e05f006">00452</a>     <a class="code" href="classgraph_1_1connect.html">connect</a>(container&amp; g) :g(g) {};
<a name="l00453"></a>00453     <span class="comment">//minimal span tree</span>
<a name="l00457"></a>00457 <span class="comment"></span>    <span class="keyword">typedef</span> std::pair&lt;T,std::pair&lt;int,int&gt; &gt; <a class="code" href="classgraph_1_1connect.html#a1d9995deb5eb3bdd3af6029e4e05f006">dist_vertex_pair</a>;
<a name="l00458"></a>00458     <span class="keyword">typedef</span> std::multimap&lt;T,std::vector&lt;int&gt; &gt; span_tree;
<a name="l00459"></a>00459      span_tree kruskal() {
<a name="l00460"></a>00460         <a class="code" href="classdisjoint__sets.html">disjoint_sets&lt;int&gt;</a> forest;
<a name="l00461"></a>00461         <span class="keyword">typename</span> std::priority_queue&lt;dist_vertex_pair,std::vector&lt;dist_vertex_pair&gt;, std::greater&lt;dist_vertex_pair&gt; &gt; q;
<a name="l00462"></a>00462         <span class="comment">//initialize </span>
<a name="l00463"></a>00463         <span class="keywordflow">for</span>(<span class="keywordtype">int</span> i=0;i&lt;g.numvertex();i++) {
<a name="l00464"></a>00464             <span class="keywordflow">for</span>(<span class="keyword">typename</span> container::edge_iterator it=g.first_edge(i);it!=g.end_edge(i);++it) {
<a name="l00465"></a>00465                 q.push(<a class="code" href="classgraph_1_1connect.html#a1d9995deb5eb3bdd3af6029e4e05f006">dist_vertex_pair</a>(it.length(),std::pair&lt;int,int&gt;(i,it.vertex())));
<a name="l00466"></a>00466             }
<a name="l00467"></a>00467             forest.addset(i);
<a name="l00468"></a>00468         }
<a name="l00469"></a>00469         <span class="keywordtype">int</span> k=0,p1,p2;
<a name="l00470"></a>00470         std::vector&lt;T&gt; sum(g.numvertex(),0);
<a name="l00471"></a>00471         <span class="keywordflow">while</span>(!q.empty()) {
<a name="l00472"></a>00472             <a class="code" href="classgraph_1_1connect.html#a1d9995deb5eb3bdd3af6029e4e05f006">dist_vertex_pair</a> t=q.top();q.pop();
<a name="l00473"></a>00473             <span class="keywordtype">int</span> u=t.second.first,v=t.second.second;
<a name="l00474"></a>00474             <span class="keywordflow">if</span>( (p1=forest.find(u))!=(p2=forest.find(v))) {
<a name="l00475"></a>00475                 sum[forest.merge(u,v)]=sum[p1]+sum[p2]+g.weight(u,v);
<a name="l00476"></a>00476                 k++;
<a name="l00477"></a>00477             }
<a name="l00478"></a>00478         }
<a name="l00479"></a>00479         <span class="comment">//organize for output </span>
<a name="l00480"></a>00480         span_tree mst;
<a name="l00481"></a>00481         disjoint_sets&lt;int&gt;::set_map r=forest.organize();
<a name="l00482"></a>00482         <span class="keywordflow">for</span>(<a class="code" href="classdisjoint__sets.html">disjoint_sets&lt;int&gt;::set_map::iterator</a> it=r.begin();it!=r.end();it++) {
<a name="l00483"></a>00483             <span class="keywordflow">if</span>(it-&gt;second.size()&gt;0) {
<a name="l00484"></a>00484                 mst.insert(<span class="keyword">typename</span> std::pair&lt;T,std::vector&lt;int&gt; &gt; (sum[it-&gt;first],it-&gt;second));
<a name="l00485"></a>00485             }
<a name="l00486"></a>00486         }
<a name="l00487"></a>00487         <span class="keywordflow">return</span> span_tree(mst);
<a name="l00488"></a>00488     }
<a name="l00489"></a>00489     <span class="comment">//Strong connected component</span>
<a name="l00490"></a>00490     <span class="comment">/*</span>
<a name="l00491"></a>00491 <span class="comment">    *  tarjan algorithm  O(N+M)</span>
<a name="l00492"></a>00492 <span class="comment">    */</span>
<a name="l00493"></a><a class="code" href="classgraph_1_1connect_1_1tarjan__visit.html">00493</a>     <span class="keyword">class </span><a class="code" href="classgraph_1_1connect_1_1tarjan__visit.html">tarjan_visit</a> {
<a name="l00494"></a>00494         std::vector&lt;int&gt;&amp; DFN;
<a name="l00495"></a>00495         std::vector&lt;int&gt;&amp; Low;
<a name="l00496"></a>00496         std::stack&lt;int&gt; s;
<a name="l00497"></a>00497         <span class="keyword">public</span>:
<a name="l00498"></a>00498         <a class="code" href="classgraph_1_1connect_1_1tarjan__visit.html">tarjan_visit</a>(std::vector&lt;int&gt;&amp; DFN,std::vector&lt;int&gt;&amp; Low): DFN(DFN),Low(Low) {
<a name="l00499"></a>00499 <span class="comment">//            DFN=std::vector&lt;int&gt; (g.numvertex(),std::numeric_limits&lt;int&gt;::max());</span>
<a name="l00500"></a>00500 <span class="comment">//            Low=std::vector&lt;int&gt; (g.numvertex(),std::numeric_limits&lt;int&gt;::max());</span>
<a name="l00501"></a>00501         };
<a name="l00502"></a>00502         <span class="keywordtype">bool</span> operator() (<span class="keywordtype">int</span> v,<span class="keywordtype">int</span> u, <span class="keywordtype">bool</span> hasOutEdge) {
<a name="l00503"></a>00503             std::cout&lt;&lt;<span class="stringliteral">&quot;Visited &quot;</span>&lt;&lt;v&lt;&lt;std::endl;
<a name="l00504"></a>00504             <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00505"></a>00505         }
<a name="l00506"></a>00506     };
<a name="l00507"></a>00507     <span class="keywordtype">void</span> tarjan(<span class="keywordtype">int</span> u) {
<a name="l00508"></a>00508         <span class="comment">//stack&lt;int&gt; s;</span>
<a name="l00509"></a>00509         <span class="comment">//vector&lt;bool&gt; visited(g.numvertex(),0);</span>
<a name="l00510"></a>00510         std::vector&lt;int&gt; DFN(g.numvertex(),std::numeric_limits&lt;int&gt;::max());
<a name="l00511"></a>00511         std::vector&lt;int&gt; Low(g.numvertex(),std::numeric_limits&lt;int&gt;::max());
<a name="l00512"></a>00512             DFN[u]=Low[u]=0;
<a name="l00513"></a>00513             <a class="code" href="classgraph_1_1explorer.html">explorer&lt;T,container&gt;</a> walk(g);
<a name="l00514"></a>00514         walk.dfs_until(u,<a class="code" href="classgraph_1_1connect_1_1tarjan__visit.html">tarjan_visit</a>(DFN,Low));
<a name="l00515"></a>00515     }
<a name="l00516"></a>00516 };
<a name="l00517"></a>00517 
<a name="l00518"></a>00518 <span class="comment">//maximum flow through the network</span>
<a name="l00519"></a>00519 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T,<span class="keyword">class</span> container=<span class="keyword">class</span> adjacent_graph&lt;T&gt; &gt;
<a name="l00520"></a><a class="code" href="classgraph_1_1flow.html">00520</a> <span class="keyword">class </span><a class="code" href="classgraph_1_1flow.html">flow</a> {
<a name="l00521"></a>00521     T Inf;
<a name="l00522"></a>00522     container&amp; g; <span class="comment">//original graph.</span>
<a name="l00523"></a>00523     <span class="keyword">public</span>:
<a name="l00524"></a>00524     <a class="code" href="classgraph_1_1flow.html">flow</a>() {
<a name="l00525"></a>00525         Inf=std::numeric_limits&lt;T&gt;::max();
<a name="l00526"></a>00526     }
<a name="l00527"></a>00527     <a class="code" href="classgraph_1_1flow.html">flow</a>(container&amp; c) : g(c) {
<a name="l00528"></a>00528         Inf=std::numeric_limits&lt;T&gt;::max();
<a name="l00529"></a>00529     }
<a name="l00534"></a><a class="code" href="classgraph_1_1flow.html#a42cfc1bb23b062632557dc948fe5f186">00534</a>     T <a class="code" href="classgraph_1_1flow.html#a42cfc1bb23b062632557dc948fe5f186">EdmondsKarp</a>(<span class="keywordtype">int</span> s,<span class="keywordtype">int</span> t) {
<a name="l00535"></a>00535         T <a class="code" href="classgraph_1_1flow.html">flow</a>=0,d; <span class="comment">//maximum flow &amp; delta increment.</span>
<a name="l00536"></a>00536         <span class="keywordtype">int</span> u;
<a name="l00537"></a>00537         container* pRemain=<span class="keyword">new</span> container;
<a name="l00538"></a>00538         *pRemain=g;
<a name="l00539"></a>00539         <a class="code" href="classgraph_1_1explorer.html">explorer&lt;T,container&gt;</a> walk(*pRemain);
<a name="l00540"></a>00540         <span class="keywordflow">while</span>(walk.bfs(s,t)) {
<a name="l00541"></a>00541            d=Inf;
<a name="l00542"></a>00542            <span class="keywordflow">for</span>(<span class="keyword">typename</span> <a class="code" href="classgraph_1_1explorer_1_1path__iterator.html">explorer&lt;T,container&gt;::path_iterator</a> it=walk.path_end(s,t);it!=walk.path_begin(s,t);--it) d=std::min(d,-it);
<a name="l00543"></a>00543            <span class="keywordflow">for</span>(<span class="keyword">typename</span> <a class="code" href="classgraph_1_1explorer_1_1path__iterator.html">explorer&lt;T,container&gt;::path_iterator</a> it=walk.path_end(s,t);it!=walk.path_begin(s,t);--it) {
<a name="l00544"></a>00544                 (-it)-=d;
<a name="l00545"></a>00545                 (+it)+=d;
<a name="l00546"></a>00546             }
<a name="l00547"></a>00547        flow+=d;
<a name="l00548"></a>00548      }
<a name="l00549"></a>00549       <span class="keyword">delete</span> pRemain;
<a name="l00550"></a>00550       <span class="keywordflow">return</span> flow;
<a name="l00551"></a>00551     }
<a name="l00556"></a><a class="code" href="classgraph_1_1flow_1_1dinic__build__level__til.html">00556</a>     <span class="keyword">class </span><a class="code" href="classgraph_1_1flow_1_1dinic__build__level__til.html">dinic_build_level_til</a> {
<a name="l00557"></a>00557             std::vector&lt;int&gt;&amp; level;
<a name="l00558"></a>00558             <span class="keywordtype">int</span> t;
<a name="l00559"></a>00559         <span class="keyword">public</span>:
<a name="l00560"></a>00560             <a class="code" href="classgraph_1_1flow_1_1dinic__build__level__til.html">dinic_build_level_til</a>(std::vector&lt;int&gt;&amp; lvl,<span class="keywordtype">int</span> end) :level(lvl),t(end) {}
<a name="l00561"></a>00561             <span class="keywordtype">bool</span> operator() (<span class="keywordtype">int</span> v,<span class="keywordtype">int</span> prev, <span class="keywordtype">bool</span> hasOutEdge) {
<a name="l00562"></a>00562                 <span class="keywordflow">if</span>(prev&gt;=0) level[v]=level[prev]+1;
<a name="l00563"></a>00563                 <span class="keywordflow">else</span> level[v]=0;
<a name="l00564"></a>00564                 <span class="keywordflow">if</span>(v==t) <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00565"></a>00565                 <span class="keywordflow">else</span> <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00566"></a>00566             }
<a name="l00567"></a>00567     };
<a name="l00568"></a>00568     <span class="keyword">template</span> &lt;<span class="keyword">class</span> _edge_type&gt;
<a name="l00569"></a><a class="code" href="classgraph_1_1flow_1_1check__dinic__level.html">00569</a>     <span class="keyword">class </span><a class="code" href="classgraph_1_1flow_1_1check__dinic__level.html">check_dinic_level</a> {
<a name="l00570"></a>00570             std::vector&lt;int&gt;&amp; level;
<a name="l00571"></a>00571     <span class="keyword">public</span>:
<a name="l00572"></a>00572         <a class="code" href="classgraph_1_1flow_1_1check__dinic__level.html">check_dinic_level</a>(std::vector&lt;int&gt;&amp; lvl) : level(lvl) {}
<a name="l00573"></a>00573         <span class="keywordtype">bool</span> operator()(<span class="keywordtype">int</span> v,<span class="keywordtype">int</span> prev,_edge_type&amp; edge) { <span class="keywordflow">return</span> (edge&gt;T()&amp;&amp;level[v]==level[prev]+1);}
<a name="l00574"></a>00574     };
<a name="l00575"></a>00575     T dinic(<span class="keywordtype">int</span> s,<span class="keywordtype">int</span> t) {
<a name="l00576"></a>00576         T <a class="code" href="classgraph_1_1flow.html">flow</a>=T(),d; <span class="comment">//maximum flow &amp; delta increment.</span>
<a name="l00577"></a>00577         <span class="keywordtype">int</span> u;
<a name="l00578"></a>00578         std::vector&lt;int&gt; level(g.numvertex(),0);
<a name="l00579"></a>00579         container* pRemain=<span class="keyword">new</span> container;
<a name="l00580"></a>00580         *pRemain=g;
<a name="l00581"></a>00581         <a class="code" href="classgraph_1_1explorer.html">explorer&lt;T,container&gt;</a> walk(*pRemain);
<a name="l00582"></a>00582         <span class="keywordflow">while</span>(walk.bfs_until(s,<a class="code" href="classgraph_1_1flow_1_1dinic__build__level__til.html">dinic_build_level_til</a>(level,t))) {
<a name="l00583"></a>00583             d=Inf;
<a name="l00584"></a>00584             <span class="keywordflow">while</span>(walk.dfs_until(s,<a class="code" href="classgraph_1_1reached__at.html">reached_at&lt;int&gt;</a>(t),<a class="code" href="classgraph_1_1flow_1_1check__dinic__level.html">check_dinic_level&lt;int&gt;</a>(level)) ) {
<a name="l00585"></a>00585                     <span class="keywordflow">for</span>(<span class="keyword">typename</span> <a class="code" href="classgraph_1_1explorer_1_1path__iterator.html">explorer&lt;T,container&gt;::path_iterator</a> it=walk.path_end(s,t);it!=walk.path_begin(s,t);--it) d=std::min(d,-it);
<a name="l00586"></a>00586                     <span class="keywordflow">for</span>(<span class="keyword">typename</span> <a class="code" href="classgraph_1_1explorer_1_1path__iterator.html">explorer&lt;T,container&gt;::path_iterator</a> it=walk.path_end(s,t);it!=walk.path_begin(s,t);--it) {
<a name="l00587"></a>00587                         (-it)-=d;(+it)+=d;
<a name="l00588"></a>00588                     }
<a name="l00589"></a>00589                     flow+=d;
<a name="l00590"></a>00590                 }
<a name="l00591"></a>00591         }
<a name="l00592"></a>00592         <span class="keyword">delete</span> pRemain;
<a name="l00593"></a>00593         <span class="keywordflow">return</span> flow;
<a name="l00594"></a>00594     }
<a name="l00603"></a>00603 };
<a name="l00604"></a>00604 
<a name="l00605"></a>00605 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T,<span class="keyword">class</span> container=<span class="keyword">class</span> adjacent_graph&lt;T&gt; &gt;
<a name="l00606"></a><a class="code" href="classgraph_1_1bipartite.html">00606</a> <span class="keyword">class </span><a class="code" href="classgraph_1_1bipartite.html">bipartite</a> {
<a name="l00607"></a>00607     T Inf;
<a name="l00608"></a>00608     container&amp; g; <span class="comment">//original graph.</span>
<a name="l00609"></a>00609     <span class="keyword">public</span>:
<a name="l00610"></a>00610     <a class="code" href="classgraph_1_1bipartite.html">bipartite</a>();
<a name="l00611"></a>00611     <a class="code" href="classgraph_1_1bipartite.html">bipartite</a>(container&amp; g) :g(g) {};
<a name="l00612"></a>00612     <span class="comment">/*</span>
<a name="l00613"></a>00613 <span class="comment">    * Hugarian Algorithm</span>
<a name="l00614"></a>00614 <span class="comment">    */</span>
<a name="l00615"></a><a class="code" href="classgraph_1_1bipartite_1_1hg__matched.html">00615</a>     <span class="keyword">class </span><a class="code" href="classgraph_1_1bipartite_1_1hg__matched.html">hg_matched</a> {
<a name="l00616"></a>00616         std::vector&lt;int&gt;&amp; match;
<a name="l00617"></a>00617         <span class="keyword">public</span>:
<a name="l00618"></a>00618             <a class="code" href="classgraph_1_1bipartite_1_1hg__matched.html">hg_matched</a>(std::vector&lt;int&gt;&amp; match) :  match(match) {}
<a name="l00619"></a>00619             <span class="keywordtype">bool</span> operator() (<span class="keywordtype">int</span> v,<span class="keywordtype">int</span> prev,<span class="keywordtype">bool</span> hasOutEdge) {
<a name="l00620"></a>00620                 <span class="keywordflow">if</span>(match[prev]&lt;0) {
<a name="l00621"></a>00621                     match[prev]=v;
<a name="l00622"></a>00622                     <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00623"></a>00623                 }
<a name="l00624"></a>00624                 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00625"></a>00625             }
<a name="l00626"></a>00626     };
<a name="l00627"></a>00627     <span class="keywordtype">int</span> hungarian() {
<a name="l00628"></a>00628         <span class="keywordtype">int</span> num_match=0;
<a name="l00629"></a>00629         <span class="keywordtype">int</span> u,t;
<a name="l00630"></a>00630         std::vector&lt;int&gt; match(g.numvertex(),-1);
<a name="l00631"></a>00631         <a class="code" href="classgraph_1_1explorer.html">explorer&lt;T,container&gt;</a> walk(g);
<a name="l00632"></a>00632         <span class="keywordflow">for</span>(<span class="keywordtype">int</span> s=0;s&lt;g.numvertex();s++) 
<a name="l00633"></a>00633             <span class="keywordflow">if</span> (walk.bfs_until(s,<a class="code" href="classgraph_1_1bipartite_1_1hg__matched.html">hg_matched</a>(match))) {
<a name="l00634"></a>00634                 num_match++;
<a name="l00635"></a>00635             }
<a name="l00636"></a>00636         <span class="keywordflow">return</span> num_match;
<a name="l00637"></a>00637     }
<a name="l00638"></a>00638     <span class="comment">/*</span>
<a name="l00639"></a>00639 <span class="comment">    *  Hopcroft-Karp Algorithm O(sqrt(n)*e)</span>
<a name="l00640"></a>00640 <span class="comment">    */</span>
<a name="l00641"></a>00641     <span class="keywordtype">int</span> Hopcroft_Karp() {
<a name="l00642"></a>00642     };
<a name="l00643"></a>00643     <span class="comment">/*</span>
<a name="l00644"></a>00644 <span class="comment">    *  Kuhn_Munkras Algorithm</span>
<a name="l00645"></a>00645 <span class="comment">    */</span>
<a name="l00646"></a>00646     <span class="keywordtype">int</span> Kuhn_Munkras(){
<a name="l00647"></a>00647     };
<a name="l00648"></a>00648 };
<a name="l00649"></a>00649 
<a name="l00650"></a>00650 <span class="comment">//cost Flow </span>
<a name="l00651"></a>00651 <span class="comment">//template &lt;class T,class container=class adjacent_graph&lt;T&gt; &gt;</span>
<a name="l00652"></a>00652 <span class="comment">//class flow : {</span>
<a name="l00653"></a>00653 <span class="comment">//        //minCost Maxinum flow</span>
<a name="l00654"></a>00654 <span class="comment">//    //each edge has two value: cost &amp; cap.</span>
<a name="l00670"></a>00670 <span class="comment"></span><span class="comment">//};</span>
<a name="l00671"></a>00671 }; <span class="comment">/* graph */</span>
<a name="l00672"></a>00672 
<a name="l00673"></a>00673 
<a name="l00674"></a>00674 <span class="preprocessor">#endif </span><span class="comment">/* __GRAPH_H__ */</span>
<a name="l00675"></a>00675 
<a name="l00676"></a>00676 
</pre></div></div><!-- contents -->
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
<a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(0)"><span class="SelectionMark">&#160;</span>All</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(1)"><span class="SelectionMark">&#160;</span>Classes</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(2)"><span class="SelectionMark">&#160;</span>Functions</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(3)"><span class="SelectionMark">&#160;</span>Typedefs</a></div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>



<hr class="footer"/><address class="footer"><small>
Generated on Sat Jan 26 2013 22:18:27 for Jamming by &#160;<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/>
</a> 1.7.6.1
</small></address>

</body>
</html>
